In the field of computers used for real-time control and simulation, there are often unique problems. This is particularly true in the field of robotics wherein the movement of multijointed arms, and the like, creates a computationally intensive environment. Inadequate computing power has always been the major obstacle in real-time implementation of advanced robotic schemes, due to the computational cost of the evaluation of required kinematic and dynamic models. Dynamic simulation of the robot arm requires even more computing power than does control. The problem becomes more difficult for direct-drive arms, representing even faster dynamics, and for redundant and multiple arms, which involve more degrees of freedom (DOF). Thus, it is widely recognized that parallel computing is the key solution for achieving required computing power for real-time control and simulation.
The parallel operation of digital computers is certainly not a new concept. So-called multi-processing has been employed in various computationally intensive environments for a long time. Likewise, it is well known to employ a large number of computing nodes linked on a token passing ring, or the like, to solve major computational problems through a technique called distributed processing wherein one node is in charge of distributing the workload among the various other nodes. Large commercial networks in the order of several hundred computers on a common ring have been employed in the off-hours, for example, to perform "ray tracing" graphics generation. When so employed, the network of smaller work stations or nodes can have a combined computing power equal to one of the multimillion dollar super computers. It is to be understood (and is well known to those skilled in the art) that the foregoing examples of multi-processing and distributed processing employ a number of stand-alone computers which accomplish their common task through the sending and receiving of messages between the computers which assign tasks, pass results, etc.
In investing the problems particularly unique to advanced robotics, the inventors herein quickly demonstrated that for kinematic and dynamic problems, particularly those required for real-time control, a pipelined architecture of a number of digital computers cannot reduce the computation time; that is, for these problems, concurrency can only be achieved by exploiting parallelism. There are, however, several problems attendant to exploiting parallelism in this particular application which must be considered. The inventors' studies on the matter resulted in the conclusion that there is a high degree of parallelism inherent in these particular computational problems. The difficulty in exploiting this parallelism results from the fact that it exists in different forms and at different levels in the computations. Attempts at exploiting this inherent parallelism with conventional parallel architectures have failed since these architectures are capable of exploiting only one type of parallelism; namely, either Single Instruction--Multiple Data (SIMD) or Multiple Instruction--Multiple Data (MIMD).
Some thought has been done by others skilled in the art in an attempt to provide a parallel computer architecture which is particularly suitable for robotic uses. In this regard, for example, there is the 1984 U.S. Pat. No. 4,467,436 of Chance et al. entitled ROBOT ARM CONTROLLER WITH COMMON BUS MEMORY. A very similar architecture is shown in the 1986 patent of Konesky (U.S. Pat. No. 4,574,345), which is not stated to be specifically for robotic use. Neither addresses the problem of optimizing a computational environment where (SIMD) and (MIMD) exist in the same problem.
There are two important features of such control computation problems that should be considered simultaneously--the asymptotic computation complexity and the size of the problem (i.e. the degrees of freedom involved). Computation complexity of almost all problems are of order O(n), where n represents the number of degrees of freedom. The inventors herein have shown that these problems all belong to Nick's Class; that is, there are existing parallel algorithms with asymptotic computation complexity (O(log.sub.2 (n))) for solving these problems; however, this parallelism is coarse grained and leads to a rather small speed-up even for highly redundant robot arms. These observations imply that for these problems the following constraints apply:
At the lowest level, parallelism exists in matrix and vector operations, which is at least as significant (and for some problems, more significant than) logarithmic parallelism. The difficulty in exploiting this type of parallelism results from the small dimensions of the matrices and vectors. Hence, unlike most other scientific computations, matrix-vector operations related to robotic simulation and control cannot be performed efficiently by classical array processors such as pipeline processors or systolic arrays.